package Sort;

import java.util.Scanner;

/**
 * @author Liangyaoyun
 */
public class ShellSortSimple {
    //希尔排序是先少人多活，后多人少活
    //即对组内排序的人逐渐变多，有序化整体增加
    public static void shellSort(int[] nums){
        if (nums.length==0&&nums==null){
            return;
        }
        int tmp;
        //相隔一定的距离抽牌比较
        int gap= nums.length/2;
        //
        //最外层循环用于控制排序工程中步长取值的迭代

            //用于选定[gap，n-1]范围内每一个元素执行以gap为间隔的插入排序操作
            for (int i = gap; i < nums.length ; i++) {
                //实现选定元素与前序下标取值间隔为gap的所有同组元素之间的比较和交换过程
                for (int j = i; j >=gap ; j-=gap) {
                    //如果前一张牌大于后面一张牌则交换位置
                    if (nums[j]<nums[j-gap]){
                        tmp=nums[j];
                        nums[j]=nums[j-gap];
                        nums[j-gap]=tmp;
                    }
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (i== nums.length-1){
                    System.out.println(nums[i]);
                }else {
                    System.out.print(nums[i]+" ");
                }
            }

    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int len=scanner.nextInt();
        int[] nums=new int[len];
        for (int i = 0; i < len; i++) {
            nums[i]= scanner.nextInt();
        }
        int plus=scanner.nextInt();
        shellSort(nums);
    }
}
